#include "Name.h"
#include "Runtime/Platform/ScopeRWLock.h"
#include "Runtime/Platform/PlatformAPI.h"
#include "Runtime/Misc/hash/CityHash.h"
#include "Runtime/Math/MathUtils.h"
#include "Runtime/String/Char.h"

namespace Alice
{
	// Increasing shards reduces contention but uses more memory and adds cache pressure.
	// Reducing contention matters when multiple threads create FNames in parallel.
	// Contention exists in some tool scenarios, for instance between main thread
	// and asset data gatherer thread during editor startup.
	// At runtime the async loading thread contends with game thread during asset loading.
#if WITH_CASE_PRESERVING_NAME
	constexpr uint32 FNamePoolShardBits = 10;
#else
	constexpr uint32 FNamePoolShardBits = 8;
#endif

	constexpr uint32 FNamePoolShards = 1 << FNamePoolShardBits;
	constexpr uint32 FNamePoolInitialSlotBits = 8;
	constexpr uint32 FNamePoolInitialSlotsPerShard = 1 << FNamePoolInitialSlotBits;
	
	static constexpr uint32 FNameMaxBlockBits = 13; // Limit block array a bit, still allowing 8k * block size = 1GB - 2G of FName entry data
	static constexpr uint32 FNameBlockOffsetBits = 16;
	static constexpr uint32 FNameMaxBlocks = 1 << FNameMaxBlockBits;
	static constexpr uint32 FNameBlockOffsets = 1 << FNameBlockOffsetBits;
	static constexpr uint32 NameEntryIdBits = FNameBlockOffsetBits + FNameMaxBlockBits;
	static constexpr uint32 NameEntryIdMask = (1 << NameEntryIdBits ) - 1;
	struct FNameSlot
	{
		// Use the remaining few bits to store a hash that can determine inequality
		// during probing without touching entry data
		static constexpr uint32 EntryIdBits = FNameMaxBlockBits + FNameBlockOffsetBits;
		static constexpr uint32 EntryIdMask = (1 << EntryIdBits) - 1;
		static constexpr uint32 ProbeHashShift = EntryIdBits;
		static constexpr uint32 ProbeHashMask = ~EntryIdMask;
		
		FNameSlot() {}
		FNameSlot(NameEntryId Value, uint32 ProbeHash)
			: IdAndHash(Value.ToUnstableInt() | ProbeHash)
		{
		}

		NameEntryId GetId() const { return NameEntryId::FromUnstableInt(IdAndHash & EntryIdMask); }
		uint32 GetProbeHash() const { return IdAndHash & ProbeHashMask; }
		
		bool operator==(FNameSlot Rhs) const { return IdAndHash == Rhs.IdAndHash; }

		bool Used() const { return !!IdAndHash;  }
	private:
		uint32 IdAndHash = 0;
	};
	int32 NameEntry::GetDataOffset()
	{
		return STRUCT_OFFSET(NameEntry, AnsiName);
	}

	/*-----------------------------------------------------------------------------
		FName helpers. 
	-----------------------------------------------------------------------------*/

	bool operator==(NameEntryHeader A, NameEntryHeader B)
	{
		return (uint16&)A == (uint16&)B;
	}
	NameHash::NameHash(uint64 Hash, int32 Len)
	{
		uint32 Hi = static_cast<uint32>(Hash >> 32);
		uint32 Lo = static_cast<uint32>(Hash);
		ShardIndex = Hi & ShardMask;
		UnmaskedSlotIndex = Lo;
		SlotProbeHash = (Hi & FNameSlot::ProbeHashMask);
		EntryProbeHeader.Len = uint16(Len);
		EntryProbeHeader.bIsWide = 0;
	}
		
	uint32 NameHash::GetProbeStart(uint32 SlotMask) const
	{
		return UnmaskedSlotIndex & SlotMask;
	}

	uint64 NameHash::AlgorithmId = 0xC1640000;
	uint32 NameHash::ShardMask = FNamePoolShards - 1;

	uint32 NameHash::GetShardIndex(uint64 Hash)
	{
		return static_cast<uint32>(Hash >> 32) & ShardMask;
	}

	uint64 NameHash::GenerateHash(const ANSICHAR* Str, int32 Len)
	{
		return CityHash64(reinterpret_cast<const char*>(Str), Len);
	}
	    
	uint32 NameHash::GetProbeStart(uint32 UnmaskedSlotIndex, uint32 SlotMask)
	{
		return UnmaskedSlotIndex & SlotMask;
	}
	template<ENameCase Sensitivity>
	FORCEINLINE bool EqualsSameDimensions(NameStringView A, NameStringView B)
	{
		const uint32 len = A.mLen;

		if (Sensitivity == ENameCase::CaseSensitive)
		{
			return !strncmp(A.mAnsiStr, B.mAnsiStr, len);
		}
		else
		{
			return !_strnicmp(A.mAnsiStr, B.mAnsiStr, len);
		}

	}

	template<ENameCase Sensitivity>
	FORCEINLINE bool Equals(NameStringView A, NameStringView B)
	{
		return (A.mLen == B.mLen) && EqualsSameDimensions<Sensitivity>(A, B);
	}

	// Minimize stack lifetime of large decode buffers
	#ifdef WITH_CUSTOM_NAME_ENCODING
	#define OUTLINE_DECODE_BUFFER FORCENOINLINE
	#else
	#define OUTLINE_DECODE_BUFFER
	#endif

	template<ENameCase Sensitivity>
	OUTLINE_DECODE_BUFFER bool EqualsSameDimensions(const NameEntry& inNameEntry, NameStringView inNameStringView)
	{
		NameBuffer DecodeBuffer;
		return EqualsSameDimensions<Sensitivity>(inNameEntry.MakeView(DecodeBuffer), inNameStringView);
	}

	/** An unpacked NameEntryId */
	struct FNameEntryHandle
	{
		uint32 Block = 0;
		uint32 Offset = 0;

		FNameEntryHandle(uint32 InBlock, uint32 InOffset)
			: Block(InBlock)
			, Offset(InOffset)
		{
		}

		FNameEntryHandle(NameEntryId Id)
			: Block(Id.ToUnstableInt() >> FNameBlockOffsetBits)
			, Offset(Id.ToUnstableInt() & (FNameBlockOffsets - 1))
		{
		}

		operator NameEntryId() const
		{
			return NameEntryId::FromUnstableInt(Block << FNameBlockOffsetBits | Offset);
		}

		explicit operator bool() const { return Block | Offset; }
	};

	static uint32 GetTypeHash(FNameEntryHandle Handle)
	{
		return (Handle.Block << (32 - FNameMaxBlockBits)) + Handle.Block // Let block index impact most hash bits
			+ (Handle.Offset << FNameBlockOffsetBits) + Handle.Offset // Let offset impact most hash bits
			+ (Handle.Offset >> 4); // Reduce impact of non-uniformly distributed entry name lengths 
	}

	uint32 GetTypeHash(NameEntryId Id)
	{
		return GetTypeHash(FNameEntryHandle(Id));
	}
	/**
	 * Thread-safe paged FNameEntry allocator
	 */
	class FNameEntryAllocator
	{
	public:
		enum { Stride = alignof(NameEntry) };
		enum { BlockSizeBytes = Stride * FNameBlockOffsets };

		/** Initializes all member variables. */
		FNameEntryAllocator()
		{
			Blocks[0] = AllocBlock();
		}

		~FNameEntryAllocator()
		{
			for (int32 Index = CurrentBlock; Index >= 0; --Index)
			{
				free(Blocks[Index]);
			}
		}

		void ReserveBlocks(uint32 Num)
		{
			WriteScopeLock _(Lock);

			for (uint32 Idx = Num - 1; Idx > CurrentBlock && Blocks[Idx] == nullptr; --Idx)
			{
				Blocks[Idx] = AllocBlock();
			}
		}


		/**
		 * Allocates the requested amount of bytes and returns an id that can be used to access them
		 *
		 * @param   Size  Size in bytes to allocate, 
		 * @return  Allocation of passed in size cast to a FNameEntry pointer.
		 */
		template <class ScopeLock, bool bNumbered = false>
		FNameEntryHandle Allocate(uint32 Bytes)
		{
			Bytes = Align(Bytes, alignof(NameEntry));
			ScopeLock _(Lock);
			AlignCurrentByteCursor<bNumbered>();

			// Allocate a new pool if current one is exhausted. We don't wory about a little bit
			// of waste at the end given the relative size of pool to average and max allocation.
			if (BlockSizeBytes - CurrentByteCursor < Bytes)
			{
				AllocateNewBlock();
				AlignCurrentByteCursor<bNumbered>();
			}

			// Use current cursor position for this allocation and increment cursor for next allocation
			uint32 ByteOffset = CurrentByteCursor;
			CurrentByteCursor += Bytes;
			
			return FNameEntryHandle(CurrentBlock, ByteOffset / Stride);
		}

		template<class ScopeLock>
		FNameEntryHandle Create(NameStringView Name, NameEntryId ComparisonId, NameEntryHeader Header)
		{
	// Silence the TSAN warning as we don't care for prefetch if we fetch the old or new value
	#if !USING_THREAD_SANITISER
			PlatformMisc::Prefetch(Blocks[CurrentBlock]);
	#endif
			FNameEntryHandle Handle = Allocate<ScopeLock>(NameEntry::GetDataOffset() + Name.BytesWithoutTerminator());
			NameEntry& Entry = Resolve(Handle);
	#if WITH_CASE_PRESERVING_NAME
			Entry.ComparisonId = ComparisonId.ToUnstableInt()==0 ? ComparisonId : NameEntryId(Handle);
	#endif
			Entry.Header = Header;
			Entry.StoreName(Name.mAnsiStr, Name.mLen);
			return Handle;
		}

		NameEntry& Resolve(FNameEntryHandle Handle) const
		{
			// Lock not needed
			return *reinterpret_cast<NameEntry*>(Blocks[Handle.Block] + Stride * Handle.Offset);
		}

		void BatchLock() const
		{
			Lock.WriteLock();
		}

		void BatchUnlock() const
		{
			Lock.WriteUnlock();
		}

		/** Returns the number of blocks that have been allocated so far for names. */
		uint32 NumBlocks() const
		{
			return CurrentBlock + 1;
		}

		uint8** GetBlocksForDebugVisualizer() { return Blocks; }

	private:
		static constexpr bool IsUnalignedNumberedEntry(uint32 BlockOffset)
		{
			return false;
		}
		
		static constexpr NameEntryHeader NumberPadHeader = {};

		// Pad up FNameEntry::NumberedName to be 4B-aligned if FNameEntry is only 2B-aligned
		template <bool bNumbered>
		void AlignCurrentByteCursor()
		{
			if (bNumbered && IsUnalignedNumberedEntry(CurrentByteCursor) && (BlockSizeBytes - CurrentByteCursor) >= sizeof(NameEntryHeader))
			{
				(NameEntryHeader&)Blocks[CurrentBlock][CurrentByteCursor] = NumberPadHeader;
				CurrentByteCursor += sizeof(NumberPadHeader);
			}	
		}

		uint8* AllocBlock()
		{
			return (uint8*)malloc(BlockSizeBytes);
		}
		
		void AllocateNewBlock()
		{
			// Null-terminate final entry to allow DebugDump() entry iteration
	#if UE_FNAME_OUTLINE_NUMBER
			if (CurrentByteCursor + NumberedEntrySize <= BlockSizeBytes)
			{
				FNameEntry* Terminator = (FNameEntry*)(Blocks[CurrentBlock] + CurrentByteCursor);
				Terminator->Header.Len = 0;
				Terminator->NumberedName = {}; // Might be unaligned but only DebugDumpBlock will read it
			}
	#else
			if (CurrentByteCursor + NameEntry::GetDataOffset() <= BlockSizeBytes)
			{
				NameEntry* Terminator = (NameEntry*)(Blocks[CurrentBlock] + CurrentByteCursor);
				Terminator->Header.Len = 0;
			}
	#endif

			++CurrentBlock;
			CurrentByteCursor = 0;

			// Allocate block unless it's already reserved
			if (Blocks[CurrentBlock] == nullptr)
			{
				Blocks[CurrentBlock] = AllocBlock();
			}
			PlatformMisc::Prefetch(Blocks[CurrentBlock]);
		}

		mutable RWLock Lock;
		uint32 CurrentBlock = 0;
		uint32 CurrentByteCursor = 0;
		uint8* Blocks[FNameMaxBlocks] = {};
	#if USE_FNAME_MMAP
		TArray<uint8*> MmappedAddresses;
		int32 MmapFile = -1;
		int32 MmapFileOffset = 0;
		int32 CurrentMmapOffset = 0;
		uint8* CurrentMmapAddress = nullptr;
	#endif
	};

	template<class CharType>
	uint64 GenerateLowerCaseHash(const CharType* Str, uint32 Len)
	{
		CharType LowerStr[NAME_SIZE];
		for (uint32 I = 0; I < Len; ++I)
		{
			LowerStr[I] = TChar<CharType>::ToLower(Str[I]);
		}
		return NameHash::GenerateHash(LowerStr, Len);
	}


	using FNameComparisonValue = NameValue<ENameCase::IgnoreCase>;
	#if WITH_CASE_PRESERVING_NAME
	using FNameDisplayValue = NameValue<ENameCase::CaseSensitive>;
	#endif

	// For pre-locked batch operations
	struct FNullScopeLock
	{
		FNullScopeLock(RWLock&) {}
	};

	// One name to be loaded in a large batch
	template<ENameCase Sensitivity>
	struct FNameLoad
	{
		NameValue<Sensitivity> In;
		FDisplayNameEntryId* Out = nullptr;
		bool bInReuseComparisonEntry = false;
		bool bOutCreatedNewEntry = false;

		void SetOut(NameEntryId Id);
	};

	using FNameComparisonLoad = FNameLoad<ENameCase::IgnoreCase>;
	template<> void FNameComparisonLoad::SetOut(NameEntryId Id) { Out->SetLoadedComparisonId(Id); }
	#if WITH_CASE_PRESERVING_NAME
	using FNameDisplayLoad = FNameLoad<ENameCase::CaseSensitive>;
	template<> void FNameDisplayLoad::SetOut(NameEntryId Id) { Out->SetLoadedDifferentDisplayId(Id); }
	#endif

	class alignas(PLATFORM_CACHE_LINE_SIZE) FNamePoolShardBase : Noncopyable
	{
	public:
		void Initialize(FNameEntryAllocator& InEntries)
		{
			Entries = &InEntries;

			Slots = (FNameSlot*)malloc(FNamePoolInitialSlotsPerShard * sizeof(FNameSlot));
			memset(Slots, 0, FNamePoolInitialSlotsPerShard * sizeof(FNameSlot));
			CapacityMask = FNamePoolInitialSlotsPerShard - 1;
		}

		// This and ~FNamePool() is not called during normal shutdown
		// but only via explicit FName::TearDown() call
		~FNamePoolShardBase()
		{
			free(Slots);
			UsedSlots = 0;
			CapacityMask = 0;
			Slots = nullptr;
			NumCreatedEntries = 0;
			NumCreatedWideEntries = 0;
		}

		uint32 Capacity() const	{ return CapacityMask + 1; }
		uint32 NumCreated() const { return NumCreatedEntries.load(std::memory_order_relaxed); }
		uint32 NumCreatedWide() const { return NumCreatedWideEntries.load(std::memory_order_relaxed); }
		uint32 NumCreatedWithNumber() const { return NumCreatedWithNumberEntries.load(std::memory_order_relaxed); }

	protected:
		enum { LoadFactorQuotient = 9, LoadFactorDivisor = 10 }; // I.e. realloc slots when 90% full

		mutable RWLock Lock;
		uint32 UsedSlots = 0;
		uint32 CapacityMask = 0;
		FNameSlot* Slots = nullptr;
		FNameEntryAllocator* Entries = nullptr;
		std::atomic<uint32> NumCreatedEntries{0};
		std::atomic<uint32> NumCreatedWideEntries{0};
		std::atomic<uint32> NumCreatedWithNumberEntries{0};


		template<ENameCase Sensitivity>
		FORCEINLINE static bool EntryEqualsValue(const NameEntry& Entry, const NameValue<Sensitivity>& Value)
		{
			// UE_FNAME_OUTLINE_NUMBER no special case handling here because entry + number entries have Len == 0 which is not true of any stored strings
			//	so the headers will compare unequal
			return Entry.Header == Value.Hash.EntryProbeHeader && EqualsSameDimensions<Sensitivity>(Entry, Value.Name);
		}
	};

	template<ENameCase Sensitivity>
	class FNamePoolShard : public FNamePoolShardBase
	{
	public:
		NameEntryId Find(const NameValue<Sensitivity>& Value) const
		{
			NameEntryId Result;
			{
				RWScopeLock _(Lock, ERWScopeLockType::SLT_ReadOnly);
				FNameSlot& Slot = Probe(Value);
				Result = Slot.GetId();
			};
			return Result;
		}

		template<class ScopeLock = WriteScopeLock>
		FORCEINLINE NameEntryId Insert(const NameValue<Sensitivity>& Value, bool& bCreatedNewEntry)
		{
			ScopeLock _(Lock);
			FNameSlot& Slot = Probe(Value);

			if (Slot.Used())
			{
				return Slot.GetId();
			}

			bCreatedNewEntry = true;
			return CreateAndInsertEntry<ScopeLock>(Slot, Value);
		}

		void InsertExistingEntry(NameHash Hash, NameEntryId ExistingId)
		{
			InsertExistingEntryImpl<WriteScopeLock>(Hash, ExistingId);
		}

	private:
		template<class ShardScopeLock>
		void InsertExistingEntryImpl(NameHash Hash, NameEntryId ExistingId)
		{
			FNameSlot NewLookup(ExistingId, Hash.SlotProbeHash);

			ShardScopeLock _(Lock);
			 
			FNameSlot& Slot = Probe(Hash.UnmaskedSlotIndex, [=](FNameSlot Old) { return Old == NewLookup; });
			if (!Slot.Used())
			{
				ClaimSlot(Slot, NewLookup);
			}
		}

	public:
		void Reserve(uint32 Num)
		{
			ReserveImpl<WriteScopeLock>(Num);
		}

	private:
		template<class ShardScopeLock>
		void ReserveImpl(uint32 Num)
		{
			// Num + 1 to compensate for division rounding down
			uint32 WantedCapacity = MathUtils::RoundUpToPowerOfTwo((Num + 1) * LoadFactorDivisor / LoadFactorQuotient);

			ShardScopeLock _(Lock);
			if (WantedCapacity > Capacity())
			{
				Grow(WantedCapacity);
			}
		}

		void ClaimSlot(FNameSlot& UnusedSlot, FNameSlot NewValue)
		{
			UnusedSlot = NewValue;

			++UsedSlots;
			if (UsedSlots * LoadFactorDivisor > LoadFactorQuotient * Capacity())
			{
				Grow();
			}
		}

		template<class EntryScopeLock>
		NameEntryId CreateAndInsertEntry(FNameSlot& Slot, const NameValue<Sensitivity>& Value)
		{
			NameEntryId NewEntryId;// = Entries->Create<EntryScopeLock>(Value.Name, Value, Value.Hash.EntryProbeHeader);

			ClaimSlot(Slot, FNameSlot(NewEntryId, Value.Hash.SlotProbeHash));

			NumCreatedEntries.fetch_add(1, std::memory_order_relaxed);
			NumCreatedWideEntries.fetch_add(false, std::memory_order_relaxed);
			
			return NewEntryId;
		}

		void Grow()
		{
			Grow(Capacity() * 2);
		}

		void Grow(const uint32 NewCapacity)
		{
			/*TArrayView<FNameSlot> OldSlots(Slots, Capacity());
			const uint32 OldUsedSlots = UsedSlots;

			Slots = (FNameSlot*)FMemory::Malloc(NewCapacity * sizeof(FNameSlot), alignof(FNameSlot));
			memset(Slots, 0, NewCapacity * sizeof(FNameSlot));
			UsedSlots = 0;
			CapacityMask = NewCapacity - 1;

			// Prefetch FNameEntry* before rehashing. Yielded 2.4x rehash speedup on a Gen5 console.
			constexpr uint32 PrefetchDepth = 8;
			FNameSlot PrefetchedSlots[PrefetchDepth];
			uint32 NumPrefetched = 0;
			
			for (FNameSlot OldSlot : OldSlots)
			{
				if (OldSlot.Used())
				{
					FPlatformMisc::Prefetch(&Entries->Resolve(OldSlot.GetId()));
					PrefetchedSlots[NumPrefetched] = OldSlot;
			
					if (++NumPrefetched == PrefetchDepth)
					{
						for (FNameSlot PrefetchedSlot : PrefetchedSlots)
						{
							RehashAndInsert(PrefetchedSlot);
						}

						NumPrefetched = 0;
					}
				}
			}

			for (FNameSlot PrefetchedSlot : MakeArrayView(PrefetchedSlots, NumPrefetched))
			{
				RehashAndInsert(PrefetchedSlot);
			}
			free(OldSlots.GetData());*/
		}

		void ProbePrefetch(const NameValue<Sensitivity>& Value) const
		{
			// Prefetch name data and FNameSlot*
			PlatformMisc::Prefetch(Value.Name.Data);
			PlatformMisc::Prefetch(Slots + NameHash::GetProbeStart(Value.Hash.UnmaskedSlotIndex, CapacityMask));
			
			// Prefetching the FNameEntry* might help, but it involves waiting for FNameSlot* 
			// and potentially a branch if we don't want to prefetch null pointers for unused slots.
			// Would probably need two prefetch passes to see a perf increase from this and
			// I'd rather avoid even more prefetching complexity. --jtorp
		}

		/** Find slot containing value or the first free slot that should be used to store it  */
		FORCEINLINE FNameSlot& Probe(const NameValue<Sensitivity>& Value) const
		{
			return Probe(Value.Hash.UnmaskedSlotIndex, 
				[&](FNameSlot Slot)	{ return Slot.GetProbeHash() == Value.Hash.SlotProbeHash && 
										EntryEqualsValue<Sensitivity>(Entries->Resolve(Slot.GetId()), Value); });
		}

		/** Find slot that fulfills predicate or the first free slot  */
		template<class PredicateFn>
		FORCEINLINE FNameSlot& Probe(uint32 UnmaskedSlotIndex, PredicateFn Predicate) const
		{
			const uint32 Mask = CapacityMask;
			for (uint32 I = NameHash::GetProbeStart(UnmaskedSlotIndex, Mask); true; I = (I + 1) & Mask)
			{
				FNameSlot& Slot = Slots[I];
				if (!Slot.Used() || Predicate(Slot))
				{
					return Slot;
				}
			}
		}
		
		void RehashAndInsert(FNameSlot OldSlot)
		{
			const NameEntry& Entry = Entries->Resolve(OldSlot.GetId());
			{
				NameBuffer DecodeBuffer;
				NameStringView Name = Entry.MakeView(DecodeBuffer);
				NameHash Hash = HashName<Sensitivity>(Name);
				FNameSlot& NewSlot = Probe(Hash.UnmaskedSlotIndex, [](FNameSlot Slot) { return false; });
				NewSlot = OldSlot;
				++UsedSlots;
			}
		}
	};


	class FNamePool
	{
	public:
		FNamePool();
		
		void Reserve(uint32 NumBlocks, uint32 NumEntries);
		NameEntryId	Store(NameStringView View);
		NameEntryId	Find(NameStringView View) const;
		/** @pre !!Handle */
		NameEntry&		Resolve(FNameEntryHandle Handle) const { return Entries.Resolve(Handle); }

		bool			IsValid(FNameEntryHandle Handle) const;

		FDisplayNameEntryId	StoreValue(const FNameComparisonValue& Value);
	#if WITH_CASE_PRESERVING_NAME
		FDisplayNameEntryId	StoreValue(const FNameDisplayValue& Value, bool bReuseComparisonId);
		bool			ReuseComparisonEntry(bool bAddedComparisonEntry, const FNameDisplayValue& DisplayValue);
	#endif
		/// Stats and debug related functions ///

		uint32			NumEntries() const;
		uint32			NumAnsiEntries() const;
		uint32			NumWideEntries() const;
		uint32			NumNumberedEntries() const;
		uint32			NumBlocks() const { return Entries.NumBlocks(); }
		uint32			NumSlots() const;

	private:
		enum { MaxENames = 512 };
		FNameEntryAllocator Entries;
	#if WITH_CASE_PRESERVING_NAME
		FNamePoolShard<ENameCase::CaseSensitive> DisplayShards[FNamePoolShards];
	#endif
		FNamePoolShard<ENameCase::IgnoreCase> ComparisonShards[FNamePoolShards];
	};

	FNamePool::FNamePool()
	{
		for (FNamePoolShardBase& Shard : ComparisonShards)
		{
			Shard.Initialize(Entries);
		}

	#if WITH_CASE_PRESERVING_NAME
		for (FNamePoolShardBase& Shard : DisplayShards)
		{
			Shard.Initialize(Entries);
		}
	#endif
	}
	NameEntryId FNamePool::Find(NameStringView Name) const
	{
	#if WITH_CASE_PRESERVING_NAME
		// Look for an exact match with the right casing first
		FNameDisplayValue DisplayValue(Name);
		if (NameEntryId Existing = DisplayShards[DisplayValue.Hash.ShardIndex].Find(DisplayValue))
		{
			return Existing;
		}
	#endif

		FNameComparisonValue ComparisonValue(Name);
		return ComparisonShards[ComparisonValue.Hash.ShardIndex].Find(ComparisonValue);
	}

	NameEntryId FNamePool::Store(NameStringView Name)
	{
	#if WITH_CASE_PRESERVING_NAME
		// Look for an exact match with the right casing first
		FNameDisplayValue DisplayValue(Name);
		if (NameEntryId Existing = DisplayShards[DisplayValue.Hash.ShardIndex].Find(DisplayValue))
		{
			return Existing;
		}
	#endif

		bool bAdded = false;

		// Insert comparison name first since display value must contain comparison name
		FNameComparisonValue ComparisonValue(Name);
		NameEntryId ComparisonId = ComparisonShards[ComparisonValue.Hash.ShardIndex].Insert(ComparisonValue, bAdded);

	#if WITH_CASE_PRESERVING_NAME
		DisplayValue.ComparisonId = ComparisonId;
		return StoreValue(DisplayValue, bAdded).ToDisplayId();
	#else
		return ComparisonId;
	#endif
	}

	FORCEINLINE FDisplayNameEntryId FNamePool::StoreValue(const FNameComparisonValue& ComparisonValue)
	{
		bool bAdded = false;
		NameEntryId ComparisonId = ComparisonShards[ComparisonValue.Hash.ShardIndex].Insert(ComparisonValue, bAdded);

#if WITH_CASE_PRESERVING_NAME
		FNameDisplayValue DisplayValue(ComparisonValue.Name);
		DisplayValue.ComparisonId = ComparisonId;
		return StoreValue(DisplayValue, bAdded);
#else
		return FDisplayNameEntryId::FromComparisonId(ComparisonId);
#endif
	}

#if WITH_CASE_PRESERVING_NAME
	bool FNamePool::ReuseComparisonEntry(bool bAddedComparisonEntry, const FNameDisplayValue& DisplayValue)
	{
		return bAddedComparisonEntry || EqualsSameDimensions<ENameCase::CaseSensitive>(Resolve(DisplayValue.ComparisonId), DisplayValue.Name);
	}

	FORCEINLINE FDisplayNameEntryId FNamePool::StoreValue(const FNameDisplayValue& DisplayValue, bool bAddedComparisonEntry)
	{
		FDisplayNameEntryId Out = FDisplayNameEntryId::FromComparisonId(DisplayValue.ComparisonId);

		FNamePoolShard<ENameCase::CaseSensitive>& DisplayShard = DisplayShards[DisplayValue.Hash.ShardIndex];
		if (ReuseComparisonEntry(bAddedComparisonEntry, DisplayValue))
		{
			DisplayShard.InsertExistingEntry(DisplayValue.Hash, DisplayValue.ComparisonId);
		}
		else
		{
			Out.SetLoadedDifferentDisplayId(DisplayShard.Insert(DisplayValue, bAddedComparisonEntry));
		}

		return Out;
	}
#endif

	uint32 FNamePool::NumEntries() const
	{
		uint32 Out = 0;
#if WITH_CASE_PRESERVING_NAME
		for (const FNamePoolShardBase& Shard : DisplayShards)
		{
			Out += Shard.NumCreated();
			Out += Shard.NumCreatedWithNumber();
		}
#endif
		for (const FNamePoolShardBase& Shard : ComparisonShards)
		{
			Out += Shard.NumCreated();
			Out += Shard.NumCreatedWithNumber();
		}

		return Out;
	}

	uint32 FNamePool::NumAnsiEntries() const
	{
		return NumEntries() - NumWideEntries() - NumNumberedEntries();
	}

	uint32 FNamePool::NumWideEntries() const
	{
		uint32 Out = 0;
#if WITH_CASE_PRESERVING_NAME
		for (const FNamePoolShardBase& Shard : DisplayShards)
		{
			Out += Shard.NumCreatedWide();
		}
#endif
		for (const FNamePoolShardBase& Shard : ComparisonShards)
		{
			Out += Shard.NumCreatedWide();
		}

		return Out;
	}

	uint32 FNamePool::NumNumberedEntries() const
	{
		uint32 Out = 0;
#if UE_FNAME_OUTLINE_NUMBER
#if WITH_CASE_PRESERVING_NAME
		for (const FNamePoolShardBase& Shard : DisplayShards)
		{
			Out += Shard.NumCreatedWithNumber();
		}
#endif
		for (const FNamePoolShardBase& Shard : ComparisonShards)
		{
			Out += Shard.NumCreatedWithNumber();
		}
#endif // UE_FNAME_OUTLINE_NUMBER

		return Out;
	}

	uint32 FNamePool::NumSlots() const
	{
		uint32 SlotCapacity = 0;
#if WITH_CASE_PRESERVING_NAME
		for (const FNamePoolShardBase& Shard : DisplayShards)
		{
			SlotCapacity += Shard.Capacity();
		}
#endif
		for (const FNamePoolShardBase& Shard : ComparisonShards)
		{
			SlotCapacity += Shard.Capacity();
		}

		return SlotCapacity;
	}

	bool FNamePool::IsValid(FNameEntryHandle Handle) const
	{
		return Handle.Block < Entries.NumBlocks();
	}

	void FNamePool::Reserve(uint32 NumBytes, uint32 InNumEntries)
	{
		uint32 NumBlocks = NumBytes / FNameEntryAllocator::BlockSizeBytes + 1;
		Entries.ReserveBlocks(NumBlocks);

		if (NumEntries() < InNumEntries)
		{
			uint32 NumEntriesPerShard = InNumEntries / FNamePoolShards + 1;

#if WITH_CASE_PRESERVING_NAME
			for (FNamePoolShard<ENameCase::CaseSensitive>& Shard : DisplayShards)
			{
				Shard.Reserve(NumEntriesPerShard);
			}
#endif
			for (FNamePoolShard<ENameCase::IgnoreCase>& Shard : ComparisonShards)
			{
				Shard.Reserve(NumEntriesPerShard);
			}
		}
	}

	static bool bNamePoolInitialized;
	alignas(FNamePool) static uint8 NamePoolData[sizeof(FNamePool)];

	// Only call this once per public FName function called
	//
	// Not using magic statics to run as little code as possible
	static FNamePool& GetNamePool()
	{
		if (bNamePoolInitialized)
		{
			return *(FNamePool*)NamePoolData;
		}

		FNamePool* Singleton = nullptr;
		
		{
			Singleton = new (NamePoolData) FNamePool;
			bNamePoolInitialized = true;
		};
		
		return *Singleton;
	}

	// Only call from functions guaranteed to run after FName lazy initialization
	static FNamePool& GetNamePoolPostInit()
	{
		return (FNamePool&)NamePoolData;
	}

	template <ENameCase SearchCase>
	static int32 CompareDifferentIdsAlphabetically(NameEntryId AId, NameEntryId BId)
	{
		FNamePool& Pool = GetNamePool();
		NameBuffer ABuffer, BBuffer;
		NameStringView AView =	Pool.Resolve(AId).MakeView(ABuffer);
		NameStringView BView =	Pool.Resolve(BId).MakeView(BBuffer);

		int32 MinLen = MathUtils::Min(AView.mLen, BView.mLen);
		int32 StrDiff;
		if (SearchCase == ENameCase::IgnoreCase)
		{
			StrDiff = strnicmp(AView.mAnsiStr, BView.mAnsiStr, MinLen);
		}
		else
		{
			StrDiff = strncmp(AView.mAnsiStr, BView.mAnsiStr, MinLen);
		}
		if (StrDiff) return StrDiff;

		return AView.mLen - BView.mLen;
	}

	int32 NameEntryId::CompareLexical(NameEntryId Rhs) const
	{
		return Value != Rhs.Value ? CompareDifferentIdsAlphabetically<ENameCase::IgnoreCase>(*this, Rhs) : 0;
	}

	int32 NameEntryId::CompareLexicalSensitive(NameEntryId Rhs) const
	{
		return Value != Rhs.Value ? CompareDifferentIdsAlphabetically<ENameCase::CaseSensitive>(*this, Rhs) : 0;
	}

	/*-----------------------------------------------------------------------------
		FNameEntry
	-----------------------------------------------------------------------------*/

	void NameEntry::StoreName(const ANSICHAR* InName, uint32 Len)
	{
		memcpy(AnsiName, InName, sizeof(ANSICHAR) * Len);
	}
	void NameEntry::CopyUnterminatedName(ANSICHAR* Out) const
	{
		memcpy(Out, AnsiName, Header.Len);
	}

	FORCEINLINE ANSICHAR const* NameEntry::GetUnterminatedName(ANSICHAR(&OptionalDecodeBuffer)[NAME_SIZE]) const
	{
#ifdef WITH_CUSTOM_NAME_ENCODING
		CopyUnterminatedName(OptionalDecodeBuffer);
		return OptionalDecodeBuffer;
#else
		return AnsiName;
#endif
	}

	FORCEINLINE NameStringView NameEntry::MakeView(NameBuffer& OptionalDecodeBuffer) const
	{
		return NameStringView(GetUnterminatedName(OptionalDecodeBuffer.AnsiName), GetNameLength());
	}

	void NameEntry::GetAnsiName(ANSICHAR(&Out)[NAME_SIZE]) const
	{
		CopyUnterminatedName(Out);
		Out[Header.Len] = '\0';
	}
	int32 NameEntry::GetSizeInBytes() const
	{
		return Align(GetDataOffset() + GetNameLength(), alignof(NameEntry));
	}

	void Name::Reserve(uint32 NumBytes, uint32 NumNames)
	{
		GetNamePoolPostInit().Reserve(NumBytes, NumNames);
	}

	int32 Name::GetNameEntryMemorySize()
	{
		return GetNamePool().NumBlocks() * FNameEntryAllocator::BlockSizeBytes;
	}

	int32 Name::GetNameEntryMemoryEstimatedAvailable()
	{
		FNamePool& Pool = GetNamePool();
		return (FNameMaxBlocks - Pool.NumBlocks()) * FNameEntryAllocator::BlockSizeBytes;
	}

	int32 Name::GetNameTableMemorySize()
	{
		return GetNameEntryMemorySize() + sizeof(FNamePool) + GetNamePool().NumSlots() * sizeof(FNameSlot);
	}

	int32 Name::GetNumAnsiNames()
	{
		return GetNamePool().NumAnsiEntries();
	}

	int32 Name::GetNumWideNames()
	{
		return GetNamePool().NumWideEntries();
	}
	
	NameEntry const* Name::GetEntry(NameEntryId Id)
	{
		// Public interface, recurse to the actual string entry if necessary
		return ResolveEntryRecursive(Id);
	}

	bool Name::IsWithinBounds(NameEntryId Id)
	{
		return GetNamePoolPostInit().IsValid(Id);
	}

	/*-----------------------------------------------------------------------------
		FName implementation.
	-----------------------------------------------------------------------------*/

	struct FNameAnsiStringView
	{
		using CharType = ANSICHAR;

		const ANSICHAR* Str;
		int32 Len;
	};

	struct FNameUtf8StringViewWithWidth
	{
		using CharType = UTF8CHAR;

		const UTF8CHAR* Str;
		int32 Len;
		bool bIsWide;
	};

	struct FWideStringViewWithWidth
	{
		using CharType = WIDECHAR;

		const WIDECHAR* Str;
		int32 Len;
		bool bIsWide;
	};

	static FNameAnsiStringView MakeUnconvertedView(const ANSICHAR* Str, int32 Len)
	{
		return { Str, Len };
	}

	static FNameAnsiStringView MakeUnconvertedView(const ANSICHAR* Str)
	{
		return { Str, Str ? int32(strlen(Str)) : 0 };
	}


	// @pre Str contains only digits and the number is smaller than int64 max
	template<typename CharType>
	static constexpr int64 Atoi64(const CharType* Str, int32 Len)
	{
		int64 N = 0;
		for (int32 Idx = 0; Idx < Len; ++Idx)
		{
			N = 10 * N + Str[Idx] - '0';
		}

		return N;
	}

	/** Templated implementations of non-templated member functions, helps keep header clean */
	struct FNameHelper
	{
		template<typename ViewType>
		static Name MakeDetectNumber(ViewType View, EFindName FindType)
		{
			if (View.Len == 0)
			{
				return Name();
			}
			
			uint32 InternalNumber = ParseNumber(View.Str, View.Len);
			return MakeWithNumber(View, FindType, InternalNumber);
		}

		static Name MakeWithNumber(FNameAnsiStringView	 View, EFindName FindType, int32 InternalNumber)
		{
			// Ignore the supplied number if the name string is empty
			// to keep the semantics of the old FName implementation
			if (View.Len == 0)
			{
				return Name();
			}

			return MakeInternal(NameStringView(View.Str, View.Len), FindType, InternalNumber);
		}

		template<typename CharType>
		static bool EqualsString(Name inName, const CharType* Str, int32 Len)
		{
			if (Len == 0)
			{
				return inName.IsNone();
			}

			// "_[num]" is considered "None" to keep semantics of old FName implementation
			if (inName.IsNone() & (Str[0] == '_'))
			{
				ParseNumber(Str, /* in-out */ Len);
				return Len == 0;
			}

			const NameEntry* Entry = Name::ResolveEntry(inName.GetComparisonIndexInternal());

			int32 Number = inName.GetNumber();

			// Check _[number] suffix first and shorten Len if it matches
			if (Number != NAME_NO_NUMBER_INTERNAL && 
				Number != ParseNumber(Str, /* in-out */ Len)) 
			{
				return false;
			}

			if (Len != Entry->GetNameLength())
			{
				return false;
			}
			
			NameBuffer Temp;
			return !_strnicmp(Str, Entry->GetUnterminatedName(Temp.AnsiName), Len);
		}

		template<typename CharType>
		static uint32 ParseNumber(const CharType* Name, int32& InOutLen)
		{
			const int32 Len = InOutLen;
			int32 Digits = 0;
			for (const CharType* It = Name + Len - 1; It >= Name && *It >= '0' && *It <= '9'; --It)
			{
				++Digits;
			}

			const CharType* FirstDigit = Name + Len - Digits;
			static constexpr int32 MaxDigitsInt32 = 10;
			if (Digits && Digits < Len && *(FirstDigit - 1) == '_' && Digits <= MaxDigitsInt32)
			{
				// check for the case where there are multiple digits after the _ and the first one
				// is a 0 ("Rocket_04"). Can't split this case. (So, we check if the first char
				// is not 0 or the length of the number is 1 (since ROcket_0 is valid)
				if (Digits == 1 || *FirstDigit != '0')
				{
					int64 Number = Atoi64(Name + Len - Digits, Digits);
					if (Number < MAX_int32)
					{
						InOutLen -= 1 + Digits;
						return static_cast<uint32>(NAME_EXTERNAL_TO_INTERNAL(Number));
					}
				}
			}

			return NAME_NO_NUMBER_INTERNAL;
		}

		// Internal helpers for Make* functions
	private:
		static Name MakeInternal(NameStringView View, EFindName FindType, int32 InternalNumber)
		{
			NameEntryIds Ids;
			{
				Ids = FindOrStoreString(View, FindType);
			}
			return MakeWithNumber(Ids, FindType, InternalNumber);
		}
		static Name MakeWithNumber(NameEntryIds BaseIds, EFindName FindType, int32 InternalNumber)
		{
			return FinalConstruct(BaseIds, InternalNumber);
		}
		// Indices have already been numbered if necessary
		// Not an FName constructor because of implementation details around UE_FNAME_OUTLINE_NUMBER that we want to hide from FName interface
#if UE_FNAME_OUTLINE_NUMBER
		static FName FinalConstruct(NameEntryIds Ids)
	#else
		static Name FinalConstruct(NameEntryIds Ids, int32 InternalNumber)
	#endif // UE_FNAME_OUTLINE_NUMBER
		{
			Name Out;
			Out.ComparisonIndex = Ids.ComparisonId;
#if WITH_CASE_PRESERVING_NAME
			Out.DisplayIndex = Ids.DisplayId;
#endif
#if !UE_FNAME_OUTLINE_NUMBER
			Out.Number = InternalNumber;
#endif
			return Out;
		}

#if WITH_CASE_PRESERVING_NAME
		static NameEntryId ResolveComparisonId(NameEntryId DisplayId)
		{
			if (DisplayId.IsNone()) { return NameEntryId(); }

			return GetNamePool().Resolve(DisplayId).ComparisonId;
		}
#else
		static NameEntryId ResolveComparisonId(NameEntryId DisplayId)
		{
			return DisplayId;
		}
#endif

		// Find or store a plain string name entry, returning both comparison and display id for it.
		// If not found, returns NAME_None for both indices.
		static NameEntryIds FindOrStoreString(NameStringView View, EFindName FindType)
		{
			NameEntryIds Result{};
			{
				{
					FNamePool& Pool = GetNamePool();

					if (FindType == FNAME_Add)
					{
						NameEntryId DisplayId = Pool.Store(View);
						Result = NameEntryIds{ ResolveComparisonId(DisplayId), DisplayId };
					}
					else
					{
						NameEntryId DisplayId = Pool.Find(View);
						Result = NameEntryIds{ ResolveComparisonId(DisplayId), DisplayId };
					}
				}
			}
			return Result;
		}
	};


#if WITH_CASE_PRESERVING_NAME
	NameEntryId Name::GetComparisonIdFromDisplayId(NameEntryId DisplayId)
	{
		return GetEntry(DisplayId)->ComparisonId;
	}
#endif


	// Resolve the entry directly referred to by LookupId
	const NameEntry* Name::ResolveEntry(NameEntryId LookupId)
	{
		return &GetNamePool().Resolve(LookupId);
	}

	// Recursively resolve through the entry referred to by LookupId to reach the allocated string entry, in the case of UE_FNAME_OUTLINE_NUMBER=1
	const NameEntry* Name::ResolveEntryRecursive(NameEntryId LookupId)
	{
		const NameEntry* Entry = ResolveEntry(LookupId);
		{
			return Entry;
		}
	}

	Name::Name(const ANSICHAR* Name, EFindName FindType)
		: Name(FNameHelper::MakeDetectNumber(MakeUnconvertedView(Name), FindType))
	{}
	
	Name::Name(int32 Len, const ANSICHAR* Name, EFindName FindType)
		: Name(FNameHelper::MakeDetectNumber(MakeUnconvertedView(Name, Len), FindType))
	{}

	Name::Name(const ANSICHAR* Name, int32 InNumber)
		: Name(FNameHelper::MakeWithNumber(MakeUnconvertedView(Name), FNAME_Add, InNumber))
	{}
	Name::Name(int32 Len, const ANSICHAR* Name, int32 InNumber)
		:Name(InNumber != NAME_NO_NUMBER_INTERNAL ? FNameHelper::MakeWithNumber(MakeUnconvertedView(Name, Len), FNAME_Add, InNumber)
			: FNameHelper::MakeDetectNumber(MakeUnconvertedView(Name, Len), FNAME_Add))
	{}
	
	int32 Name::Compare( const Name& Other ) const
	{
		// Names match, check whether numbers match.
		if (GetComparisonIndex() == Other.GetComparisonIndex())
		{
			return GetNumber() - Other.GetNumber();
		}

		// Names don't match. This means we don't even need to check numbers.
		return CompareDifferentIdsAlphabetically<ENameCase::IgnoreCase>(GetComparisonIndex(), Other.GetComparisonIndex());
	}

	void Name::GetPlainANSIString(ANSICHAR(&AnsiName)[NAME_SIZE]) const
	{
		GetDisplayNameEntry()->GetAnsiName(AnsiName);
	}
	
	const NameEntry* Name::GetComparisonNameEntry() const
	{
		return ResolveEntryRecursive(GetComparisonIndexInternal());
	}

	const NameEntry* Name::GetDisplayNameEntry() const
	{
		return ResolveEntryRecursive(GetDisplayIndexInternal());
	}

	uint32 Name::GetStringLength() const
	{
		const NameEntry& Entry = *GetDisplayNameEntry();
		uint32 NameLen = Entry.GetNameLength();

		if (GetNumber() != NAME_NO_NUMBER_INTERNAL)
		{
			// Return the length of the number suffix "_<num>"
			// We only need to actually compute the size past values of 9.
			// The minimum suffix length is 2, including the one for a suffix value of 0.
			NameLen += 2;
			for (int32 Num = NAME_INTERNAL_TO_EXTERNAL(GetNumber()); Num >= 10; Num /= 10)
			{
				++NameLen;
			}
		}
		return NameLen;
	}

	template <typename CharType, int N>
	void CheckLazyName(const CharType(&Literal)[N])
	{
		CharType Literal2[N];
		strcpy(Literal2, Literal);
		constexpr ENameCase ComparisonMode =
	#if WITH_CASE_PRESERVING_NAME
			ENameCase::CaseSensitive;
#else
				ENameCase::IgnoreCase;
#endif
	}
	
	void Name::TearDown()
	{
		if (bNamePoolInitialized)
		{
			GetNamePoolPostInit().~FNamePool();
			bNamePoolInitialized = false;
		}
	}
}